package primary.code05_Tree;

import java.util.LinkedList;
import java.util.Queue;

/**
 * 宽度优先遍历
 * 采用队列辅助结构
 */
public class Code02_BreadthFirstTraversal {

    /**
     * 宽度优先遍历
     *
     * @param root
     */
    public static void bfs(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {//注意条件
            Node cur = queue.poll();
            System.out.print("  " + cur.data);
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

    public static void bfsTest(Node root) {
        if (root == null) {
            return;
        }
        Queue<Node> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            Node cur = queue.poll();
            System.out.print(cur.data + "\t");
            if (cur.left != null) {
                queue.add(cur.left);
            }
            if (cur.right != null) {
                queue.add(cur.right);
            }
        }
    }

    public static void main(String[] args) {
        //构造树结构测试用
        Node a = new Node(1);
        Node b = new Node(2);
        Node c = new Node(3);
        Node d = new Node(4);
        Node e = new Node(5);
        Node f = new Node(6);
        Node g = new Node(7);
        a.left = b;
        a.right = c;
        b.right = d;
        c.left = e;
        c.right = f;
        f.left = g;

        bfs(a); // 1  2  3  4  5  6  7
        System.out.println();
        System.out.println("==========");
        bfsTest(a);
        System.out.println("\n==========");
    }
}
